package com.kevinkk.tree;

/**
 * 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
 * 创建一个根节点，其值为 nums 中的最大值。
 * 递归地在最大值 左边 的 子数组前缀上 构建左子树。
 * 递归地在最大值 右边 的 子数组后缀上 构建右子树。
 * 返回 nums 构建的 最大二叉树 。
 */

public class MaximumBinaryTree {
    class Solution {
        public TreeNode constructMaximumBinaryTree(int[] nums) {
            int length = nums.length;
            if (length == 0) return null;
            int maxIndex = getMax(nums);
            TreeNode root = new TreeNode(nums[maxIndex]);

            int[] left = new int[maxIndex];
            int[] right = new int[length - maxIndex - 1];
            System.arraycopy(nums, 0, left, 0, maxIndex);
            System.arraycopy(nums, maxIndex + 1, right, 0, length - maxIndex - 1);
            root.left = constructMaximumBinaryTree(left);
            root.right = constructMaximumBinaryTree(right);
            return root;

        }

        private int getMax(int[] nums) {
            int index = 0;
            int max = nums[index];
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] > max) {
                    max = nums[i];
                    index = i;
                }
            }
            return index;
        }
    }
}
